package Top101K;

/**
 * @Author quan
 * @Description 链表中环的入口节点
 * @Date 2023/12/6 12:01
 */
public class BM7_EntryNodeOfLoop {
    /**
     * 结论：当快慢指针相遇的时候，定义一个指针开始从起点位置运动，当新指针追上慢指针的时候，新指针所指的位置就是环的入口
     * 遍历的结束条件是什么？
     给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null
     * @param pHead
     * @return
     */
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        // 边界条件
        if(pHead == null || pHead.next == null){
            return null;
        }
        // 1-定义快慢指针
        ListNode fast = pHead;
        ListNode low = pHead;
        while (fast.next != null && fast.next.next!=null){
            fast = fast.next.next;
            low = low.next;
            // 2-当快慢指针相遇，定义新指针
            if(fast.val == low.val){
                ListNode cur = pHead;
                // 3-新指针与慢指针一定会在环的入口处相遇
                while(low != cur){
                    cur = cur.next;
                    low = low.next;
                }
                return cur;
            }
        }
        return null;
    }
}
